/**
 * 
 */
package datastructure;

import java.util.LinkedList;

/**
 * http://en.wikibooks.org/wiki/Data_Structures/Hash_Tables#Open_addressing
 * 
 * @author michaelyi
 *
 */
public class MyHashTableChain<K, V> implements MyHashTable<K, V> {

	LinkedList<Cell<K, V>>[] data;

	@Override
	public void clear() {

	}

	@Override
	public boolean containsKey(Object key) {
		return getLinkedListIndex(key) < 0 ? false : true;
	}

	@Override
	public boolean containsValue(Object value) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public V get(Object key) {
		int linkedListIndex = getLinkedListIndex(key);
		return linkedListIndex < 0 ? null : data[key.hashCode() % size()]
				.get(linkedListIndex).value;
	}

	private int getLinkedListIndex(Object key) {
		int result = -1;
		if (key == null)
			return result;

		int index = key.hashCode() % size();
		LinkedList<Cell<K, V>> list = data[index];

		if (list != null) {
			for (int i = 0; i < list.size(); ++i) {
				if (list.get(i).key.equals(key)) {
					result = i;
					break;
				}
			}
		}

		return result;
	}

	@Override
	public V put(K key, V value) {
		if (key == null)
			return null;

		int index = key.hashCode() % size();
		LinkedList<Cell<K, V>> list = data[index];
		if (list == null) {
			list = new LinkedList<Cell<K, V>>();
		} else {
			for (int i = 0; i < data[index].size(); ++i) {
				if (list.get(i).key.equals(key)) {
					list.remove(i);
					break;
				}
			}
		}
		list.addFirst(new Cell<K, V>(key, value));
		return value;
	}

	@Override
	public V remove(Object key) {
		V result = null;
		if (key == null)
			return result;

		int index = key.hashCode() % size();
		LinkedList<Cell<K, V>> list = data[index];

		if (list != null) {
			for (int i = 0; i < list.size(); ++i) {
				if (list.get(i).key.equals(key)) {
					result = list.remove(i).value;
				}
			}
		}

		return result;
	}

	@Override
	public int size() {
		return data.length;
	}

	/**
	 * 
	 */
	public MyHashTableChain() {
		this(10);
	}

	/**
	 * 
	 */
	@SuppressWarnings("unchecked")
	public MyHashTableChain(int size) {
		if (size < 0)
			size = 10;
		data = (LinkedList<Cell<K, V>>[]) new LinkedList[size];
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

	@SuppressWarnings("hiding")
	private class Cell<K, V> {
		private K key;
		private V value;

		Cell(K key, V value) {
			this.key = key;
			this.value = value;
		}

		@SuppressWarnings("unused")
		K getKey() {
			return key;
		}

		@SuppressWarnings("unused")
		void setKey(K key) {
			this.key = key;
		}

	}

}
